/*************************************
* 1、编写一个算法，将线性链表分解为两个带头结点的循环链表，
* 循环链表的长度存储字头结点的数据域中。
* 分解的规则是将序号为奇数的结点分解到第一个链表中；
* 偶数结点分解到第二个链表中。
**************************************/

#include<stdio.h>
#include<malloc.h>

struct NODE;
typedef struct NODE node;
struct NODE{int data;node* next;};

void print_linkedlist(const node* p){
    p=p->next;
    while(p){printf("%d ",p->data);p = p->next;}
    putchar('\n');}

void print_circular(const node* p){
    int i = p->data;
    while(i--)printf("%d ",(p = p->next)->data);putchar('\n');}

void del_circular(node* h){
    node* p;
    while(h->data--){p = h->next; h->next = p->next; free(p);} }

// add data to the end tof the list no sort
void append(node* h,int data){
    while(h->next)h=h->next;
    h->next = malloc(sizeof(node));
    h = h->next;
    h->data = data;
    h->next = NULL;}

// spilt one linkedlist(h) into two circular linkedlists(ha,hb)
void split(node* h,node* ha,node* hb){
    int cnt = 0;
    node* p,*q,*a,*b;
    a = ha;
    b = hb;
    ha->data = 0;
    hb->data = 0;
    while(h->next){
        cnt++;
        if(cnt&1){
            p = a->next;
            a->next = h->next;
            h->next = h->next->next;
            a = a->next;
            a->next = p;
            ha->data++;
        }else{
            p = b->next;
            b->next = h->next;
            h->next = h->next->next;
            b = b->next;
            b->next = p;
            hb->data++;
        }
    }
    // in the end, a and b are tails of the list
    // make circles
    a->next = ha->next;
    b->next = hb->next;
}


int main(){
    node head;
    node* h = &head;
    h->data = 11;
    h->next = NULL;

    int i = 0;
    int A[11] = {1,2,3,4,5,6,7,8,9,10,11};

    for(i=0;i<h->data;i++)append(h,A[i]);

    printf("List: ");print_linkedlist(h);

    node head_a;
    node* ha = &head_a;
    ha->next = NULL;

    node head_b;
    node* hb = &head_b;
    hb->next = NULL;

    split(h,ha,hb);

    printf("ha: "); print_circular(ha);
    printf("hb: "); print_circular(hb);

    del_circular(ha);
    del_circular(hb);
    return 0;
}
